package com.cat.slidingWindow;

/**
 * @author 曲大人的喵
 * @description http://leetcode.cn/problems/shortest-and-lexicographically-smallest-beautiful-string/
 * @create 2025/9/17 17:33
 * @since JDK17
 */

public class Solution38 {
    public String shortestBeautifulSubstring(String s, int k) {
        char[] arr = s.toCharArray();
        int n = arr.length, cnt = 0;
        String ans = "1".repeat(n + 1);
        for (int l = 0, r = 0; r < n; r++) {
            cnt += arr[r] - '0';    // '1' 就++
            while (cnt >= k) {
                String t = s.substring(l, r + 1);
                if (t.length() < ans.length() || t.length() == ans.length() && t.compareTo(ans) < 0) { //
                    System.out.println(ans);
                    ans = t;
                }
                cnt -= arr[l++] - '0';
            }
        }

        return ans.equals("1".repeat(n + 1)) ? "" : ans;
    }
}
